package weekMatch.one_347;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LeeCode_04 {
    public static void main(String[] args) {
        System.out.println(maxIncreasingCells(new int[][]{{3, 1, 6}, {-9, 5, 7}}));
        System.out.println(maxIncreasingCells(new int[][]{{1,1}, {1,1}}));
        System.out.println(maxIncreasingCells(new int[][]{{0, -1}, {-6,-6}, {-1, 8}}));
    }
    private static int maxIncreasingCells(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                list.add(new int[]{i, j});
            }
        }
        list.sort((o1, o2) -> mat[o2[0]][o2[1]] - mat[o1[0]][o1[1]]);
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(dp[i], 1);
        }
        int[] cows = new int[m];
        int[] rows = new int[n];
        List<int[]> tmp = new ArrayList<>();
        int pre = mat[list.get(0)[0]][list.get(0)[1]];
        for (int[] loc : list) {
            int x = loc[0], y = loc[1], num = mat[x][y];
            if (num != pre) {
                for (int[] son : tmp) {
                    int tx = son[0], ty = son[1];
                    dp[tx][ty] = Math.max(cows[tx], rows[ty]) + 1;
                }
                for (int[] son : tmp) {
                    int tx = son[0], ty = son[1];
                    cows[tx] = Math.max(cows[tx], dp[tx][ty]);
                    rows[ty] = Math.max(rows[ty], dp[tx][ty]);
                }
                tmp.clear();
                tmp.add(new int[]{x, y});
                pre = num;
            }else {
                tmp.add(new int[]{x, y});
            }
        }
        for (int[] son : tmp) {
            int tx = son[0], ty = son[1];
            dp[tx][ty] = Math.max(cows[tx], rows[ty]) + 1;
        }
        for (int[] son : tmp) {
            int tx = son[0], ty = son[1];
            cows[tx] = Math.max(cows[tx], dp[tx][ty]);
            rows[ty] = Math.max(rows[ty], dp[tx][ty]);
        }
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans = Math.max(ans, dp[i][j]);
            }
        }
        return ans;
    }
}
